//
// Created by ASUS on 2024/11/19/星期二.
//
// Problem: P4568 [JLOI2011] 飞行路线
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4568
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// DateTime : 2024-11-19 22:25:00
// Author : sunyafei
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define int long long

//n个节点，m条边，k层，从start到end的最短路

void solve(){
	int n,m,k;cin>>n>>m>>k;
	int start,end;cin>>start>>end;
	vector<vector<pair<int,int>>> g(n*(k+1));
	for(int i=0;i<m;i++){
		int u,v,c;cin>>u>>v>>c;
		for(int j=0;j<=k;j++){
			g[u+j*n].emplace_back(v+j*n,c);
			g[v+j*n].emplace_back(u+j*n,c);
			if(j>0){
				g[u+(j-1)*n].emplace_back(v+j*n,0);
				g[v+(j-1)*n].emplace_back(u+j*n,0);
			}
		}
	}
	vector<int> dis(n*(k+1),INT_MAX/2);
	dis[start]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
	pq.emplace(0,start);
	while(!pq.empty()){
		auto [dx,x]=pq.top();
		pq.pop();
		if(dis[x]<dx) continue;
		for(auto&[y,d]:g[x]){
			int new_dis=d+dx;
			if(new_dis<dis[y]){
				dis[y]=new_dis;
				pq.emplace(new_dis,y);
			}
		}
	}
	int ans=INT_MAX;
	for(int i=0;i<=k;i++){
		ans=min(ans,dis[n*i+end]);
	}
	cout<<ans;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t=1;
	//cin>>t;
	while(t--){
		solve();
		cout<<"\n";
	}

	return 0;
}
